package solution;


import java.util.*;

/**
 * DepthFirstPaths.java
 * @param <V>
 * ------------------------------------------------------------------------
 * The s-t connectivity problem.
 * - Given source vertex s and a target vertex t, is there a path between s and t?
 */
public class DepthFirstPaths<V> {
    private Set<V> marked;

    // <顶点, 父顶点>
    private Map<V, V> edgeTo;

    private V s;

    public DepthFirstPaths(Graph<V> graph, V s) {
        this.edgeTo = new HashMap<>();
        this.marked = new HashSet<>();
        this.s = s;

        dfs(graph, s);
    }

    private void dfs(Graph<V> graph, V v) {
        marked.add(v);
        for (Edge<V> edge : graph.neighbors(v)) {
            V w = edge.getTo();
            if (!marked.contains(w)) {
                edgeTo.put(w, v);
                dfs(graph, w);
            }
        }
    }

    public boolean hasPathTo(V v){
        return marked.contains(v);
    }

    public Iterable<V> pathTo(V v){
        if (!hasPathTo(v)) {
            return null;
        }
        List<V> path = new ArrayList<>();

        for (V x = v; x != s; x = edgeTo.get(x)) {
            path.add(x);
        }

        path.add(s);

        Collections.reverse(path);
        return path;
    }


}
